package leetcode3;

import java.util.Arrays;
import java.util.Stack;
//最小栈
class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    //正常插入栈，最小栈保持是最小的元素
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty()) {
            minStack.push(val);
        }else {
            int top = minStack.peek();
            if(val <= top) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        if(stack.isEmpty()) return;
        int top = stack.pop();
        if(top == minStack.peek()) minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

public class Day15 {


    /**
     * 判断出栈顺序
     * @param pushV
     * @param popV
     * @return
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        //1.把入栈数组入栈
        //2.判断出栈数组的数是否和栈顶元素相等，相等就出栈，不相等则说明不能出栈
        //3.遍历完数组后，如果出栈数组还未遍历完说明false

        int j=0;//遍历出栈数组
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<pushV.length;i++) {
            stack.push(pushV[i]);
            //判断是否需要出栈
            while(j<popV.length && !stack.isEmpty() &&stack.peek()==popV[j]) {
                stack.pop();
                j++;
            }
        }
        if(j>=popV.length) {
            return true;
        }
        return false;
    }


    //逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        //1.数字入栈
        //2.如果是表达式，那么连续出栈两次，第一次出栈的数放在表达式右边
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<tokens.length;i++) {
            String s = tokens[i];
            //判断是数字还是字符
            int t = isOperator(s);
            if(t != -1) {
                //是操作符
                int num1 = stack.pop();
                int num2 = stack.pop();
                int num;
                if(t==1) {
                    //+
                    num = num1 + num2;
                }else if(t==2) {
                    //-
                    num = num2 - num1;
                }else if(t==3) {
                    //*
                    num = num2 * num1;
                }else {
                    //  /
                    num = (int)(num2 / num1) ;
                }
                stack.push(num);
            }else {
                //不是操作符
                int num = Integer.parseInt(s);
                stack.push(num);
            }
        }
        return stack.pop();
    }

    //判断是否为操作符
    private int isOperator(String s) {
        // 1:+  2:-   3:*   4:\   -1:数字
        if(s.equals("+")) {
            return 1;
        } else if (s.equals("-")) {
            return 2;
        } else if (s.equals("*")) {
            return 3;
        } else if (s.equals("/")) {
            return 4;
        }
        return -1;
    }

    public static void main(String[] args) {

    }
}
